Thực đơn
Thuật_toán_Prim Độ phức tạp tính toánCấu trúc dữ liệu tìm cạnh có trọng số nhỏ nhất | Độ phức tạp thời gian (tổng cộng) |
---|---|
Tìm kiếm trên ma trận kề | O(V2) |
Đống nhị phân và danh sách kề | O((V + E) log V) = O(E log V) |
Đống Fibonacci và danh sách kề | O(E + V log V) |
Một cách lập trình đơn giản sử dụng ma trận kề và tìm kiếm toàn bộ mảng để tìm cạnh có trọng số nhỏ nhất có thời gian chạy O(V2). Bằng cách sử dụng cấu trúc dữ liệu đống nhị phân và danh sách kề, có thể giảm thời gian chạy xuống O(E log V). Bằng cách sử dụng cấu trúc dữ liệu đống Fibonacci phức tạp hơn, có thể giảm thời gian chạy xuống O(E + V log V), nhanh hơn thuật toán trước khi đồ thị có số cạnh E=ω(V).
Thực đơn
Thuật_toán_Prim Độ phức tạp tính toánLiên quan
Thuật ngữ giải phẫu cử động Thuật toán Thuật ngữ anime và manga Thuật ngữ lý thuyết đồ thị Thuật ngữ thiên văn học Thuật chiêu hồn Thuật toán Dijkstra Thuật ngữ tin học Thuật ngữ ngữ âm học Thuật toán sắp xếpTài liệu tham khảo
WikiPedia: Thuật_toán_Prim http://www.mincel.com/java/prim.html http://people.csail.mit.edu/rivest/programs.html http://students.ceid.upatras.gr/~papagel/project/p... https://web.archive.org/web/20060712152157/http://... https://commons.wikimedia.org/wiki/Category:Prim's...